package HighMethod01;

/**
 * 斐波那契数列
 */
public class test02 {

    //递归    有重复计算
    public static int Fibo(int n){
        if(n == 1||n == 2)
            return 1;
        return Fibo(n-1) + Fibo(n-2);
    }   //时间：O(2*N)  最坏的时间复杂度是o  空间：S(n)

    //递归2
    public  static int fib(int n){
        int a = 1,b=1;
        return fib(n,a,b);
    }
    public static int fib(int n,int a, int b){
        if (n <= 2) return 1;
        else  return fib(n-1,a+b,a);
    }


    //非递归  动归
    public static int Fibo2(int n){
        int result = 0;
        int a = 1;
        int b = 1;

        if(n == 1||n == 2)
            return 1;

        for(int i = 3;i<=n;i++){
            result = a+ b;
            a = b;
            b = result;
        }
        return result;
    }

    //递归的优化,空间换时间
    public static int FiboOptim(int n){
        int []arr = new int[99];
        arr[0] = 0;
        arr[1] = 1;
        arr[2] = 1;
        for(int i=3;i<=n;i++){
            arr[i]=arr[i-1]+arr[i-2];
        }
        return arr[n];
    }


    public static void main(String[] args) {
        System.out.println(Fibo2(6));
        System.out.println(Fibo(6));
        System.out.println(FiboOptim(6));
    }
}
